Embodiments described herein relate generally to packet classification, and, in particular, to packet classification based on range values.
A data packet received at a network device can be processed based on one or more policies established by, for example, a network administrator. Any processing performed so that the data packet can be subsequently processed at the network device based on a policy can be referred to as packet classification. Packet classification can include, for example, associating the data packet with an appropriate policy from a library of policies based on information included in the data packet such as an address value and/or a port value. A packet classification scheme can be used to, for example, distinguish and route groups of data packets within a firewall or through a switch fabric associated with a multi-stage switch.
Known packet classification schemes, such as those based on Ternary Content Addressed Memories (TCAMs) or software algorithms, can have power requirements, chip area requirements, efficiency characteristics, and/or storage requirements that may be undesirable in some applications. For example, known software packet classification algorithms that rely on relatively large data structures resident in external memory (external to a processing chip) may have memory bandwidth limitations that can make their use in very high speed switches and routers impractical. Power consumption requirements and/or inefficient chip designs associated with some known packet classification schemes may substantially prevent scaling of these packet classification schemes, for example, for use in a complex routing system such as a data center.
Thus, a need exists for methods and apparatus for packet classification that have desirable power, chip area, efficiency, and/or storage characteristics.